#include "../tools.h"

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int size = 0;
        ListNode *p = head;
        while(p != nullptr){
            ++size;
            p = p->next;
        }
        // cout << size << endl;

        ListNode headpre(-1, head);
        ListNode *h1, *e1, *h2, *e2, *left, *right;
        int interval = 1;
        while(interval < size){
            left = &headpre, right = headpre.next;
            while(right != nullptr){
                h1 = right;
                for(int i = 0; right != nullptr && i < interval; ++i){ right = right->next;}
                if(right == nullptr) break;
                e1 = right;
                h2 = right;
                for(int i = 0; right != nullptr && i < interval; ++i){ right = right->next;}
                e2 = right;

                // merge
                while(h1 != e1 && h2 != e2){
                    if(h1->val < h2->val) {left->next = h1; h1 = h1->next;}
                    else {left->next = h2; h2 = h2->next;}
                    left = left->next;
                }
                if(h1 != e1){
                    left->next = h1;
                    while(left->next != e1) left = left->next;
                    left->next = right;
                }
                if(h2 != e2){
                    left->next = h2;
                    while(left->next != e2) left = left->next;
                    // left->next = right;
                    
                }
                // left = right;
            }


            interval *= 2;
        }


        return headpre.next;
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;
    
    vector<int> data = {4,2,1,3};
    ListNode* head = create_list(data);
    show(head);

    ListNode* p = sol.sortList(head);
    show(p);


    return 0;
}